#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;



class RBnode//节点类
{
public:
	RBnode(int x)
	{
		data = x;
		left = NULL;
		right =NULL;
		prve = NULL;
		RB = 1;
	}
	int data;//数据
	class RBnode* left;//左节点
	class RBnode* right;//右节点
	class RBnode* prve;//父节点
	bool RB;//0是黑1是红

};

class RBfree//红黑树
{
public://调用模块
	RBfree()//析构
	{
		null = new class RBnode(-1);
		null->RB = 0;
		null->left = null;
		null->right = null;
		gen = null;
	}

	bool erase(int x)
	{
		return _erase(gen,x);
	}

	void preorder()//前序遍历
	{
		_preorder(gen);
	}

	void inorder()//中序遍历
	{
		_inorder(gen);
	}

	void Postorder()//后序遍历
	{
		_Postorder(gen);
	}

	void insert(int x)//插入
	{
		_insert(x);
	}

	int deque()//深度
	{
		return	_deque(gen);
	}

	int find(int x)//查找
	{
		return _find(gen,x);
	}

private://功能模块

	int _find(class RBnode* node, int x)//查找
	{
		if (node == null)//如果查到边境
		{
			return -1;//返回-1
		}
		if (node->data == x)//如果查找到
		{
			return x;//返回x
		}

		if (x < node->data)//如果小于此节点的数据
		{
			_find(node->left, x);//递归左孩子
		}
		else//否则
		{
			_find(node->right, x);//递归右节点
		}
	}

	void _preorder(class RBnode* node)//前序遍历
	{
		cout << node->data;//输出值
		node->RB == 1? printf("(红) ") : printf("(黑) ");//此节点颜色为1输出红否则输出黑
		if (node->left != null)//此节点左节点不等于边境
		{
			_preorder(node->left);//左节点递归
		}
		if (node->right != null)//此节点右节点不等于边境
		{
			_preorder(node->right);
		}
	}

	void _inorder(class RBnode* node)//中序遍历
	{
		if (node->left != null)//左节点不等于边境
		{
			_inorder(node->left);//左节点递归
		}
		cout << node->data;//输出数据
		node->RB == 1 ? printf("(红) ") : printf("(黑) ");//此节点颜色节点等于1输出红否则输出黑
		if (node->right != null)//右节点不等于边境
		{
			_inorder(node->right);//右节点递归
		}
	}

	void _Postorder(class RBnode* node)//后序遍历
	{
		if (node->left != null)//此节点左节点不等于边境
		{
			_Postorder(node->left);//左节点递归
		}
		if (node->right != null)//此节点右节点不等于边境
		{
			_Postorder(node->right);//右节点递归
		}
		cout << node->data;//输出值
		node->RB == 1? printf("(红) ") : printf("(黑) ");//如果这个节点颜色为1输出红否则输出黑
	}

	int _deque(class RBnode* node)//深度
	{
		int a = node->left != null ? _deque(node->left) : 0;//如果左节点不等于哨兵就递归如果等于就返回0
		int b = node->right != null ? _deque(node->right) : 0;//如果右节点不等于哨兵就递归如果等于就返回0
		return 1 + max(a,b);//筛选最大的值
	}

private://插入模块
	class RBnode* null;//哨兵或边界
	class RBnode* gen;//原根

	void _insert(int x)//插入
	{
		class RBnode* tmop1 = gen;//临时节点等于根节点
		class RBnode* tmopprve = null;//临时父亲节点

		// 找到插入位置
		while (tmop1 != null)//如果tmop1不等于边境则继续循环
		{
			tmopprve = tmop1;//临时父亲节点等于临时节点
			if (x < tmop1->data)//x小于临时节点数据时
			{
				tmop1 = tmop1->left;//临时节点朝左根移动
			}
			else //否则
			{
				tmop1 = tmop1->right;//临时节点朝右移动
			}
		}

		// 创建新节点
		class RBnode* tmop2 = new RBnode(x);//创造临时节点2
		tmop2->left = null;//临时节点2左右节点都是边境节点
		tmop2->right = null;
		tmop2->prve = tmopprve;//临时节点的父亲等于临时父亲节点

		if (tmopprve == null)//如果临时父亲节点等于边境节点
		{
			gen = tmop2;//根节点等于临时节点2
		}
		else if (x < tmopprve->data) //x小于临时父亲节点的数据
		{
			tmopprve->left = tmop2;//让临时父亲节点左节点等于临时节点2
		}
		else //否则
		{
			tmopprve->right = tmop2;//让临时父亲节点右节点等于临时节点2
		}

		insertpBUG(tmop2);// 修复红黑树性质
	}

	void insertpBUG(class RBnode* node)//检查红黑树的特性
	{

		if (node->prve == null)//如果这个节点是根节点
		{
			node->RB = 0;//根叶黑的特性根节点一直都是特性
			return;
		}
		
		if (node->prve->RB == 0)//如果父节点是黑色叶子的话直接返回，因为不违反根叶黑和不红红的特性
		{
			return;
		}

		class RBnode* fq = node->prve;//获取此节点的父亲节点
		class RBnode* yeye = fq->prve;//获取父亲节点的父亲节点简称爷爷节点
		class RBnode* shu = yeye->left == fq ? yeye->right : yeye->left;//获取叔叔节点
		if (shu->RB == 1&&fq->RB == 1)//如果叔叔节点和父亲节点都是红叶子并且不违法上面的特性
		{
			swap(shu->RB,yeye->RB);//叔叔节点和父亲的颜色和爷爷节点的颜色交换
			fq->RB = shu->RB;
			insertpBUG(yeye);//递归重新检查有没有违反特性
			return;
		}
		
		if (fq->RB == 1&&shu->RB == 0&&shu == yeye->left)//父亲节点为红色并且叔叔节点为黑色并且叔叔节点是在爷爷就带你的左边
		{
			if (fq->right->RB == 1)//父亲节点右边为红色
			{
				leftrotate(yeye);//爷爷节点左旋转
				yeye->RB = 1;//爷爷节点颜色为红色
				fq->RB = 0;//父亲节点颜色为黑色
			}
			else
			{
				rightrotate(yeye->right);//爷爷节点右子树右旋转
			    leftrotate(yeye);//爷爷节点再左旋转
				node->RB = 0;//儿子节点颜色变为黑色
				yeye->RB = 1;//爷爷节点颜色变为红色
			}
		}
		else if (fq->RB == 1 && shu->RB == 0 && shu == yeye->right)//父亲接待为红色并且叔叔节点为黑色并且叔叔节点是爷爷节点的右子树
		{
			if (fq->left->RB == 1 )//父亲节点左子树颜色是红色
			{
				rightrotate(yeye);//右旋转爷爷节点
				yeye->RB = 1;//爷爷节点颜色变红
				fq->RB = 0;//父亲节点变黑色
			}
			else
			{
				leftrotate(yeye->left);//左子树左旋转
				rightrotate(yeye);//然后再右旋转
				node->RB = 0;//子节点颜色变黑色
				yeye->RB = 1;//爷爷节点颜色变红色
			}
		}
	}

	void rightrotate(class RBnode* node)//右旋
	{
		class RBnode* tmop = node->left;//获取爷爷节点的左节点
		node->left = tmop->right;//获取爷爷节点左节点连上刚刚获取的临时节点的右节点
		if (tmop->right != null) //如果如果临时节点右节点还有孩子节点
		{
			tmop->right->prve = node;//改变临时节点右节点的父亲指向指向刚刚链接上的爷爷节点
		}
		tmop->prve = node->prve;//临时节点的父亲指向等于爷爷节点的父亲指向
		if (node->prve == null)//如果爷爷节点的父亲指向是根节点
		{
			gen = tmop;//根节点等于临时节点
		}
		else if (node == node->prve->right)//如果爷爷节点是在祖宗节点的右边的话
		{
			node->prve->right = tmop;//让祖宗节点右链接到临时节点
		}
		else //不在祖宗节点的右边那就是在左边
		{
			node->prve->left = tmop;//让祖宗节点左节点链接到临时节点
		}
		tmop->right = node;//临时节点右节点链接爷爷节点
		node->prve = tmop;//爷爷节点的父亲节点改变指向临时节点
	}

	void leftrotate(class RBnode* tmop)//左旋
	{
		class RBnode* node = tmop->right;//获取爷爷节点的右节点
		tmop->right = node->left;//获取爷爷节点右节点连上刚刚获取的临时节点的左节点
		if (node->left != null)//如果如果临时节点左节点还有孩子节点
		{
			node->left->prve = tmop;//改变临时节点左节点的父亲指向指向刚刚链接上的爷爷节点
		}
		node->prve = tmop->prve;//临时节点的父亲指向等于爷爷节点的父亲指向
		if (tmop->prve == null)//如果爷爷节点的父亲指向是根节点
		{
			gen = node;//根节点等于临时节点
		}
		else if (tmop == tmop->prve->left)//如果爷爷节点是在祖宗节点的左边的话
		{
			tmop->prve->left = node;//让祖宗节点左链接到临时节点
		}
		else //不在祖宗节点的右边那就是在右边
		{
			tmop->prve->right = node;//让祖宗节点右节点链接到临时节点
		}
		node->left = tmop;//临时节点左节点链接爷爷节点
		tmop->prve = node;//爷爷节点的父亲节点改变指向临时节点
	}

private://删除模块

	void righteraserotate(class RBnode* node) //右删除旋转
	{
		class RBnode* yeye = node->prve;//记录爷爷节点
		class RBnode* fq = yeye->left;//记录父亲节点
		if (fq->left->RB == 1)//只要父亲节点的左子树是红色节点就属于RR型
		{
			fq->left->RB = fq->RB;//儿子节点颜色变成父亲节点颜色
			fq->RB = yeye->RB;//父亲节点颜色变成爷爷节点颜色
			rightrotate(yeye);//以爷爷节点为根右旋转
		}
		else//否则就是RL型
		{
			fq->left->RB = yeye->RB;//儿子节点颜色变成爷爷节点颜色
			leftrotate(fq);//先让父亲节点左旋转
			rightrotate(yeye);//再让爷爷节点右旋转
		}
	}

	void lefteraserotate(class RBnode* node)//左删除旋转
	{
		class RBnode* yeye = node->prve;
		class RBnode* fq = yeye->right;
		if (fq->right->RB == 1)//只要父亲节点的左子树是红色节点就属于LL型
		{
			fq->right->RB = fq->RB;//儿子节点颜色变成父亲节点颜色
			fq->RB = yeye->RB;//父亲节点颜色变成爷爷节点颜色
			leftrotate(yeye);//以爷爷节点为根左旋转
		}
		else//否则就是LR型
		{
			fq->left->RB = yeye->RB;//儿子节点颜色变成爷爷节点颜色
			rightrotate(fq);//先让父亲节点右旋转
			leftrotate(yeye);//再让爷爷节点左旋转
		}
	}

	bool _erase(class RBnode* node, int x)//删除
	{
		while (node->data != x)//如果该节点是要找的数据
		{
			if (node == null)//此数没有该数据
			{
				return -1;//返回-1
			}

			if (x < node->data)//查找数据大于该节点的数据
			{
				node = node->left;//该节点向左移动

			}
			else//不是大于就是小于
			{
				node = node->right;//向右移动
			}
		}

		if (node->left != null && node->right != null)//如果要删除的节点有左右子树
		{
			class RBnode* xz = node->left;//用一个指针来查找该节点的前驱
			while (xz->right != null)//如果找到的边界直接停止
			{
				xz = xz->right;//一直向右移动
			}
			swap(xz->data, node->data);//前驱节点跟要删除的节点数据做交换
			return _erase(xz, x);//递归查询该节点删除是哪种类型的;
		}

		if (node->RB == 1 && node->left == null && node->right == null)//如果是左右子树都没有的红节点
		{
			class RBnode* tmop = node->prve;//临时变量来记录他的父节点
			if (tmop->left == node)//如果他在父节点的左子树
			{
				tmop->left = null;//让父节点的左子树指向边境
			}
			else//不是在左就是在右
			{
				tmop->right = null;//让父节的右子树指向边境
			}
			delete node;//释放内存
			return 1;
		}

		if (((node->left->RB == 1 && node->right == null) || (node->right->RB == 1 && node->left == null)) && node->RB == 0)//((左子树是红色节点并且右子树是边境)或者(右子树颜色是红色并且左子树是边境))并且自己是黑色
		{
			if (node->left->RB == 1)//如果左子树是红色
			{
				class RBnode* tmop = node->left;//临时变量记录左子树
				tmop->RB = 0;//左子树变黑
				tmop->prve = node->prve;//父节点交换
				if (node->prve == null)//如果被删节点是根节点
				{
					gen = tmop;//更新根节点
				}
				else if (node == node->prve->left)//如果被删节点等于被删节点的父节点的左子树
				{
					node->prve->left = tmop;//被删节点的父亲节点的左子树连接临时变量
				}
				else//不是左子树就是右子树
				{
					node->prve->right = tmop;//被删节点的父亲节点的右子树连接临时变量
				}
				delete node;//内存释放
				return 1;
			}
			else//不是左子树就是右子树
			{
				class RBnode* tmop = node->right;//临时变量记录右子树
				tmop->RB = 0;//右子树变黑
				tmop->prve = node->prve;//父节点交换
				if (node->prve == null)//如果被删节点是根节点
				{
					gen = tmop;//更新根节点
				}
				else if (node == node->prve->left)//如果被删节点等于被删节点的父节点的左子树
				{
					node->prve->left = tmop;//被删节点的父亲节点的左子树连接临时变量
				}
				else//不是左子树就是右子树
				{
					node->prve->right = tmop;//被删节点的父亲节点的右子树连接临时变量
				}
				delete node;//内存释放
				return 1;
			}
		}


		if (node->RB == 0 && node->prve->left == node && node->prve->right->RB == 0)//删除节点是黑色并且删除节点是在父亲节点的左子树并且兄弟节点是黑色
		{
			class RBnode* yeye = node->prve;//记录爷爷节点
			class RBnode* xd = yeye->right;//记录xd节点
			if (xd->left->RB == 1 || xd->right->RB == 1)//如果兄弟节点左右子树不为黑节点
			{
				lefteraserotate(node);//左删除旋转
			}
			else
			{
				if (yeye->RB == 0)//如果爷爷节点是黑节点
				{
					if (yeye->prve == null)//爷爷节点是根节点
					{
						xd->RB = 1;//兄弟节点变红节点
					}
					else//否则
					{
						xd->RB = 1;//兄弟节点变红
						lefteraserotate(yeye);//爷爷节点作为参数传进该函数
					}
				}
				else//不是黑节点就是红节点
				{
					yeye->RB = 0;//改变爷爷节点的颜色
				}
			}
			yeye->left = null;//爷爷节点左子树指向边境
			delete node;//内存释放
			return 1;
		}
		else if (node->RB == 0 && node->prve->right == node && node->prve->left->RB == 0)//删除节点是黑色并且删除节点是在父亲节点的右子树并且兄弟节点是黑色
		{
			class RBnode* yeye = node->prve;//记录爷爷节点
			class RBnode* xd = yeye->left;//记录xd节点
			if (xd->left->RB == 1 || xd->right->RB == 1)//如果兄弟节点左右子树不为黑节点
			{

				righteraserotate(node);//右删除旋转
			}
			else
			{
				if (yeye->RB == 0)//如果爷爷节点是黑节点
				{
					if (yeye->prve == null)//爷爷节点是根节点
					{
						xd->RB = 1;//兄弟节点变红节点
					}
					else//否则
					{
						xd->RB = 1;//兄弟节点变红
						righteraserotate(yeye);//爷爷节点作为参数传进该函数

					}
				}
				else//不是黑节点就是红节点
				{
					yeye->RB = 0;//爷爷节点变黑
				}
			}
			yeye->right = null;//爷爷节点右子树指向边境
			delete node;//内存释放
			return 1;
		}

		if (node->RB == 0 && node->prve->left == node && node->prve->right->RB == 1)//该节点为黑节点并且该节点是自己父亲节点的左子树并且父亲节点的右子树是红色
		{
			class RBnode* yeye = node->prve;//爷爷节点
			class RBnode* xd = yeye->right;//兄弟节点
			yeye->RB = 1;//爷爷节点变红
			xd->RB = 0;//兄弟节点变黑
			leftrotate(yeye);//左删除旋转爷爷节点作为参数
			_erase(node, x);//递归查找是否属于其他特性
		}
		else if (node->RB == 0 && node->prve->right == node && node->prve->left->RB == 1)//该节点为黑节点并且该节点是自己父亲节点的右子树并且父亲节点的左子树是红色
		{
			class RBnode* yeye = node->prve;//爷爷节点
			class RBnode* xd = yeye->left;//兄弟节点
			yeye->RB = 1;//爷爷节点变红
			xd->RB = 0;//兄弟节点变黑
			rightrotate(yeye);//右删除旋转爷爷节点作为参数
			_erase(node, x);//递归查找是否属于其他特性
		}
	}

};
	

int main()
{
	/*
		红黑树是一种红黑相交的树红不能连着黑可以，他的好处是插入快查找比平衡树慢一些，但是插入和删除比较赋值要灵活运用红黑树的特性
		红黑树不需要像AVL树（平衡树）那样对比平衡值这对节点做平衡没有那么严格，这使得它查找会比平衡树慢一些，但是他的插入比平衡树快
		凭借这个优点使得红黑树的地位颇高。
		删除红黑树极其复杂特性繁多注意的点也繁多，因为黑路同这个特性使得红黑树的删除并没有AVL树和排序二叉树那样轻松
	*/

	class RBfree p;
	int arr[12] = { 15,9,6,13,10,18,17,27,23,25,34,37 };
	for (long long i = 0;i< 12;i++)
	{
		p.insert(arr[i]);
	}
	cout << "插入完后：" << endl;
	cout << "红黑树的深度：" << p.deque() << endl;
	cout << "前序遍历：" << endl;
	p.preorder();
	cout << endl;
	cout << "中序遍历：" << endl;
	p.inorder();
	cout << endl;
	cout << endl;

	for (int i = 0;i<12;i++)
	{
		p.erase(arr[i]);
		cout << "删除掉：" << arr[i] << "后"<<endl;
		cout << "红黑树的深度：" << p.deque() << endl;
		cout << "前序遍历：" << endl;
		p.preorder();
		cout << endl;
		cout << "中序遍历：" << endl;
		p.inorder();
		cout << endl;
		cout << endl;
	}
	cout << "无数据";
	return 0;
}